#include <errno.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdbool.h>

#include "ursax.h"
#include "utcache.h"
#include "uthash.h"
#include "identity-pool.h"
#include "debug.h"

struct foo_hash_entry {
	uint64_t key;
	void* data;
	UT_hash_handle hh;
	int reference;
};

struct foo_hash {
	struct foo_hash_entry* entries;
	foo_destructor free_cb;
	size_t max_entries;
};

static struct identity_pool* entry_pool = NULL;

static void* new_entry()
{
	struct foo_hash_entry* entry = (struct foo_hash_entry*)malloc(sizeof(*entry));
	return entry;
}

static void delete_entry(void* data)
{
	free(data);
}

static inline struct foo_hash* uthash_create(size_t capacity, foo_destructor free_cb)
{
	if (entry_pool == NULL)
		entry_pool = identity_pool_new(1024*16*6, &new_entry, &delete_entry);

	struct foo_hash* hash = (struct foo_hash*)malloc(sizeof(*hash));
	hash->free_cb = free_cb ? free_cb : &free;
	hash->max_entries = capacity;
	hash->entries = NULL;
	return hash;	
}

static inline void uthash_add(struct foo_hash* hash, struct foo_hash_entry* entry)
{
	HASH_ADD(hh, hash->entries, key, sizeof(entry->key), entry);
}

static inline struct foo_hash_entry* uthash_add_new(struct foo_hash* hash, uint64_t key, void* data)
{
	struct foo_hash_entry* entry = (struct foo_hash_entry*)identity_pool_get(entry_pool);
	entry->key = key;
	entry->data = data;
	entry->reference = 0;
	uthash_add(hash, entry);
	return entry;
}

static inline struct foo_hash_entry* uthash_find(struct foo_hash* hash, uint64_t key)
{
	struct foo_hash_entry* entry = NULL;
	HASH_FIND(hh, hash->entries, &key, sizeof(key), entry);
	return entry;
}

static inline unsigned int uthash_count(struct foo_hash* hash)
{
	return HASH_COUNT(hash->entries);
}

static inline void uthash_del(struct foo_hash* hash, struct foo_hash_entry* entry)
{
	HASH_DEL(hash->entries, entry);
}

static inline void uthash_remove(struct foo_hash* hash, struct foo_hash_entry* entry)
{
	uthash_del(hash, entry);
	identity_pool_put(entry_pool, entry);
}

static inline uint32_t uthash_remove_some(struct foo_hash* hash, uint32_t n)
{
	if (unlikely(n == 0))
		return 0;

	uint32_t amount = 0;
	struct foo_hash_entry* entry = ELMT_FROM_HH(hash->entries->hh.tbl, hash->entries->hh.tbl->tail);
	while(entry != NULL)
	{
		struct foo_hash_entry* prev = entry->hh.prev;
		if (likely(entry->reference == 0))
		{
			uthash_remove(hash, entry);
			hash->free_cb(entry->data);
			++amount;
		}
		entry = prev;

		if (amount == n)
			break;
	}
	return amount;
}

static inline void uthash_remove_oldest(struct foo_hash* hash)
{
	uthash_remove_some(hash, 1);
}

static inline int uthash_iterate(struct foo_hash* hash, iteration_callback callback, void* arg)
{
	struct foo_hash_entry* entry, *tmp_entry;
	HASH_ITER(hh, hash->entries, entry, tmp_entry)
	{
		int ret = callback(entry->key, entry->data, arg);
		if (ret < 0)
			return ret;
	}
	return 0;
}

static inline int uthash_iterate_reference(struct foo_hash* hash, iteration_callback_reference callback, void* arg)
{
	struct foo_hash_entry* entry, *tmp_entry;
	HASH_ITER(hh, hash->entries, entry, tmp_entry)
	{
		int ret = callback(entry->key, entry->data, arg, entry->reference);
		if (ret < 0)
			return ret;
	}
	return 0;
}

static inline int uthash_delete(struct foo_hash* hash, int keep_data)
{
	if (keep_data) 
	{
		HASH_CLEAR(hh, hash->entries);
	} 
	else 
	{
		uthash_remove_some(hash, uthash_count(hash));
	}
	free(hash);
	return 0;
}

void foo_destructor_noop(void* data) { (void)data; }


/********************************************* hash table *********************************/

// create a hash table instance, optionally providing a dtor of hash table item
// the default dtor is free(void*)
// returns the pointer to the instance (always sucessful)
struct foo_hashtable* foo_hashtable_create(foo_destructor free_cb)
{
	return (struct foo_hashtable*)uthash_create(-1, free_cb);	
}

// insert a key and item pair into the hash table
// returns 0 for success, -EINVAL for failure (key is found in hash table)
int foo_hashtable_put(struct foo_hashtable* ht, uint64_t key, void* data)
{
	struct foo_hash* hash = (struct foo_hash*)ht;
	if (uthash_find(hash, key))
		return -EINVAL;		// found duplicated keys

	uthash_add_new(hash, key, data);
	return 0;
}

// look for a key in the hash table
// returns 0 for not found, 1 for found
int foo_hashtable_lookup(struct foo_hashtable* ht, uint64_t key)
{
	return (int)!!uthash_find((struct foo_hash*)ht, key);
}

// get the corresponding item of a key
// returns 0 for success, -EINVAL for failure (key not found)
int foo_hashtable_get(struct foo_hashtable* ht, uint64_t key, void* result)
{
	struct foo_hash* hash = (struct foo_hash*)ht;
	struct foo_hash_entry* entry = uthash_find(hash, key);
	if (!entry)
		return -EINVAL;

	*(void**)result = entry->data;
	return 0;
}

// return the count of items in the hash table
unsigned int foo_hashtable_entry_count(struct foo_hashtable* ht)
{
	return uthash_count((struct foo_hash*)ht);
}

// remove a key from the hash table, either get the corresponding item by *result, or destruct it 
// returns 0 for success, -EINVAL for failure (key not found)
int foo_hashtable_remove(struct foo_hashtable* ht, uint64_t key, void* result)
{
	struct foo_hash* hash = (struct foo_hash*)ht;
	struct foo_hash_entry* entry = uthash_find(hash, key);
	if (!entry)		// not found
		return -EINVAL;

	if (result) {
		*(void**)result = entry->data;
	} else {
		hash->free_cb(entry->data);
	}

	uthash_remove(hash, entry);
	return 0;
}

// iterate the items in the hash table through callback function
// the iteration is terminated if the callback returns negative int
// returns 0 for success, or the value that callback() returns when terminated
int foo_hashtable_iterate(struct foo_hashtable* ht, iteration_callback callback, void* arg)
{
	return uthash_iterate((struct foo_hash*)ht, callback, arg);
}

// delete the hash table, optionally and the items in it
// returns 0 for success (always)
int foo_hashtable_delete(struct foo_hashtable* ht, int keep_data)
{
	return uthash_delete((struct foo_hash*)ht, keep_data);
}


/**************************************** cache *******************************/
static uint32_t n_ac = 0;
static struct foo_cache* ac_array[16];

// create a cache instance, optionally providing a dtor of cache item
// the default dtor is free(void*)
// returns the pointer to the instance (always sucessful)
struct foo_cache* foo_cache_create(size_t capacity, foo_destructor free_cb, bool auto_compaction)
{
	struct foo_cache* cache = (struct foo_cache*)uthash_create(capacity, free_cb);
	if (auto_compaction && n_ac < sizeof(ac_array) / sizeof(ac_array[0]))
		ac_array[ n_ac++ ] = cache;

	int size1 = sizeof(cache);
//	int size2 = sizeof(struct foo_cache);
//	printf("size: %d", size1);

	return cache;
}

// delete the cache, optionally and the items in it
// returns 0 for success (always)
int foo_cache_delete(struct foo_cache* cache, int keep_data)
{
	return uthash_delete((struct foo_hash*)cache, keep_data);
}

// look for a key in the cache, and optionally get the corresponding item, if found
// returns 0 for not found, 1 for found
int foo_cache_lookup(struct foo_cache* cache, uint64_t key)
{
	return foo_hashtable_lookup((struct foo_hashtable*)cache, key);
}

// get the corresponding item of a key, and remove it from the cache
// returns 0 for success, -EINVAL for failure (key not found)
int foo_cache_get(struct foo_cache* cache, uint64_t key, void* result)
{
	struct foo_hash* hash = (struct foo_hash*)cache;
	struct foo_hash_entry* entry = uthash_find(hash, key);
	if (!entry)
		return -EINVAL;

	*(void**)result = entry->data;
	uthash_remove(hash, entry);
	return 0;
}

// get the corresponding item of a key, and mark it as most recently used, and increase its number of reference
// returns 0 for success, -EINVAL for failure (key not found)
int foo_cache_get_reference(struct foo_cache* cache, uint64_t key, void* result)
{
	struct foo_hash* hash = (struct foo_hash*)cache;
	struct foo_hash_entry* entry = uthash_find(hash, key);
	if (!entry)
		return -EINVAL;

	*(void**)result = entry->data;
	uthash_del(hash, entry);
	uthash_add(hash, entry);
	entry->reference++;
	if(unlikely(entry->reference > REFERENCE_MAX)){
		debug_reference(entry->reference);
	}
	return entry->reference;
}

// adjust the number of reference
// returns the number of reference after the adjust, -EINVAL for failure (key not found)
int foo_cache_adjust_reference(struct foo_cache* cache, uint64_t key, int16_t delta)
{
	struct foo_hash* hash = (struct foo_hash*)cache;
	struct foo_hash_entry* entry = uthash_find(hash, key);
	if (!entry)
		return -EINVAL;
	
	entry->reference += (int)delta;
	if(unlikely(entry->reference < 0 || entry->reference > REFERENCE_MAX)){
		debug_reference(entry->reference);
	}
	return entry->reference;
}

// remove a key from the cache, either get the corresponding item by *result, or destruct it 
// returns 0 for success, -EINVAL for failure (key not found)
int foo_cache_remove(struct foo_cache* cache, uint64_t key, void* result)
{
	return foo_hashtable_remove((struct foo_hashtable*)cache, key, result);
}

// insert a key and item pair into the cache
// returns 0 for success, -EINVAL for failure (key is found in cache)
int foo_cache_put(struct foo_cache* cache, uint64_t key, void* data)
{
	struct foo_hash* hash = (struct foo_hash*)cache;
	if (uthash_find(hash, key))
		return -EINVAL;		// found duplicated keys

	if (unlikely(uthash_count(hash) >= hash->max_entries) /*&& unlikely(count > 1)*/)
	{
		uthash_remove_oldest(hash);
	}

	uthash_add_new(hash, key, data);
	return 0;
}

// if (the key is found in cache) {entry->reference--;}
// else {insert a key and item pair into the cache, with its initial reference;}
// return entry->reference;
int foo_cache_put_reference(struct foo_cache* cache, uint64_t key, void* data, uint32_t initial_reference)
{
	struct foo_hash* hash = (struct foo_hash*)cache;
	struct foo_hash_entry* entry = uthash_find(hash, key);

	if (likely(entry != NULL))
	{
		entry->reference--;
		if(entry->reference < 0){
			LOG_ERROR("error reference < 0, and set to 0");
			entry->reference = 0;
		}
		return entry->reference;
	}

	if (unlikely( uthash_count(hash) >= hash->max_entries ) /*&& unlikely(count > 1)*/)
	{
		uthash_remove_oldest(hash);
	}

	entry = uthash_add_new(hash, key, data);
	return entry->reference = initial_reference;
}

int foo_cache_change_data(struct foo_cache* cache, uint64_t key, void* newdata)
{
	LOG_DEBUG("foo_cache_change_data data %016lx, key %016lx", newdata, key);
	struct foo_hash* hash = (struct foo_hash*)cache;
	struct foo_hash_entry* entry = uthash_find(hash, key);

	if(likely(entry != NULL)){
		entry->data = newdata;
		return 0;
	}
	return -EINVAL; // not find
}

// release some amount of entries of the cache
// returns the number actually released
int foo_cache_release(struct foo_cache* cache, uint32_t amount)
{
	return uthash_remove_some((struct foo_hash*)cache, amount);
}

// release some amount of entries from anyc cache that allows auto_compaction
// returns the number actually released
int foo_cache_release_any()
{
	uint32_t n = 0;		// total number of entries
	for (uint32_t i=0; i<n_ac; ++i)
		n += foo_cache_entry_count( ac_array[i] );

	if (unlikely(n==0))
		return 0;

	uint32_t x;	// to release x entries
	if (n > 100) {
		x = n / 5;
	} else if (n > 20) {
		x = 20;
	} else {
		x = n;
	}

	uint32_t z0 = 0;
	while(x > 0)
	{
		uint32_t z = 0;	// entries released in this iteration
		for (uint32_t i=0; i<n_ac; ++i)
		{	// to release y entries from ac_array[i]
			uint32_t y = foo_cache_entry_count( ac_array[i] );
			if (y == 0) continue;
			y = ((uint64_t)y * x + n/2) / n;
			if (y == 0) continue;
			z += foo_cache_release(ac_array[i], y);
		}
		if (z == 0)
			break;
		n -= z;
		x -= z;
		z0 += z;
	}
	return z0;
}

// return the count of items in the cache
unsigned int foo_cache_entry_count(struct foo_cache* cache)
{
	return uthash_count((struct foo_hash*)cache);
}

// iterate the items in the cache through callback function
// the iteration is terminated if the callback returns negative int
// returns 0 for success, or the value that callback() returns when terminated
int foo_cache_item_iterate(struct foo_cache *cache, iteration_callback callback, void* arg)
{
	return uthash_iterate((struct foo_hash*)cache, callback, arg);
}

int foo_cache_item_iterate_reference(struct foo_cache *cache, iteration_callback_reference callback, void* arg)
{
	return uthash_iterate_reference((struct foo_hash*)cache, callback, arg);
}


